package chapter1;

/**
 * create by yongli on 2021-07-05 21:59
 * 最具挑战性算法是证明欧几里得算法
 */

public class Section1 {

    public static int i = 0;

    public static void main(String[] args) {
        int[] ac={3,3,4,4,34,34,34,34444};
        System.out.println(rankFirst(34,ac));
        System.out.println(rankFirst(3,ac));
        System.out.println(rankFirst(4,ac));
    }

    /**
     * 熟练写出二分算法的真不多,
     * 思路很明确，就是其边界问题，
     */
    public static int rank(int target,int[] arr){
        // 闭区间
        int low=0,high = arr.length-1;
        while (low<=high){
            int mid=(low+high)/2;
            if(arr[mid]<target){
                low =mid+1;
            }else if(arr[mid]>target){
                high = mid-1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    public static int rankFirst(int target,int[] arr){
        // 闭区间
        int low=0,high = arr.length-1;
        while (low<=high){
            int mid=(low+high)/2;
            if(arr[mid]<target){
                low =mid+1;
            }else if(arr[mid]>target){
                high = mid-1;
            }else{
                // 该分支至少存在,遍历就可以了，没必要再二分
                while(arr[mid]==target){
                    if(mid==0){
                        return 0;
                    }
                    mid--;
                }
                return mid+1;
            }
        }
        return -1;
    }

    public static double bi(int N, int K, double p) {
        double[][] matrix = new double[N + 1][K + 1];
        double[] pexp = new double[N];
        double[] uexp = new double[N];

        pexp[0] = 1;
        uexp[0] = 1;
        for (int i = 2; i < N; i++) {
            pexp[i] = p * pexp[i - 1];
            uexp[i] = (1 - p) * uexp[i - 1];
        }
        for (int i = 1; i <= N; i++) {
            // 第一列
            for (int j = 1; j <= K; j++) {
                matrix[i][1] = i * p * uexp[i - 1];
            }
        }

        for (int i = 1; i <= K; i++) {
            // 第一列
            for (int j = i; j <= N; j++) {
                matrix[j][i] = i*p*uexp[j-i];
                matrix[i][1] = i * p * uexp[i - 1];
            }
        }



        return matrix[N][K];
    }

    /***
     * 以前做的题，程序化实现,也即公式程序化
     * C(t,c)*(p)^c*(1-p)^(t-c)
     * 有没有递归的方式？
     * 动态规划的思想，数学归纳法
     * 这个递归是指数增长，不好
     * 得使用非递归实现
     * 有很大的重叠区
     */
    public static double binomial(int total, int count, double p) {
        if (total == 0 && count == 0) {
            return 1.0;
        }
        // 无效的
        if (total < 0 || count < 0) {
            return 0.0;
        }
        i++;
        // 爬楼梯
        return (1.0 - p) * binomial(total - 1, count, p) + p * binomial(total, count - 1, p);
    }

    /**
     * 计算log2N,
     * lg8 = 3, lg7 = 2,
     *
     * @return
     */
    public static int lg(int n) {
//        int res =1, i=0;
//        while(res < n){
//            i++;
//           res = res<<1;
//        }
//        // 小心把握边界
//        return i-1;
        int res = 1, i = 0;
        for (; res <= n; i++) {
            res <<= 1;
        }
        return i - 1;
    }

    public static String exeR1(int n) {
        if (n < 0) {
            return "";
        }
        // 某种相同的子结构
        return exeR1(n - 2) + n + exeR1(n - 3) + n;
    }

    /**
     * 应该是一个精制转换
     *
     * @param a
     * @param b
     * @return
     */
    public static int mystery(int a, int b) {
        if (b == 0) {
            return 0;
        }
        if (b % 2 == 0) {
            return mystery(a + a, b / 2);
        } else {
            // a最后用了一下，怪怪的
            return mystery(a + a, b / 2) + a;
        }
    }

    public static void boundry() {
        int[] a = new int[10];
        for (int i = 0; i < 10; i++) {
            a[i] = 9 - i;
        }
        // 画图
        for (int i = 0; i < 10; i++) {
            a[i] = a[a[i]];
        }
        // 1.8
//        Arrays.asList(a).forEach(System.out::println);
        for (int i = 0; i < 10; i++) {
            System.out.println(a[i]);
        }

    }


    /**
     * 1000 + 999 +
     */

    public static void c117() {
        double t = 1.0;
        while (Math.abs(t - 3.0 / t) > 0.01) {
            t = (3.0 / t + t) / 2.0;
        }
        System.out.printf("%.5f", t);
    }


    public static void chafen() {
        // 迷惑性
        int f = 0, g = 1;
        for (int i = 0; i <= 15; i++) {
            System.out.println(f);
            f = f + g;
            // 按照顺序，是可以替换的， f，1,2,4
            // (0,1),(1,0),(1,1),(2,0),(2,2),(4,0),(4,4),(8,0)
            // (0,1),(1,0),(1,1),(2,1),(3,2),(5,3),
            g = f - g;
        }
    }

    public static String toBinaryString(int N) {
        // 高位和低位的问题
        String s = "";
        while (N > 0) {
            // 置于后
            s = N % 2 + s;
            N /= 2;
        }
        return s;
    }


}
